//给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。 
//
// k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 
//
// 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,2,3,4,5], k = 2
//输出：[2,1,4,3,5]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：head = [1,2,3,4,5], k = 3
//输出：[3,2,1,4,5]
// 
//
// 
//提示：
//
// 
// 链表中的节点数目为 n 
// 1 <= k <= n <= 5000 
// 0 <= Node.val <= 1000 
// 
//
// 
//
// 进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？ 
//
// 
// 
//
// Related Topics 递归 链表 👍 2120 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-08-15 01:31:22
 * @description 25.K 个一组翻转链表
 */
public class ReverseNodesInKGroup{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new ReverseNodesInKGroup().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

  //Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
     ListNode() {}
      ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
		 /*有问题*/
	public ListNode reverseKGroup3(ListNode head, int k) {
		int t=0;
		ListNode res=new ListNode(0,head);
		ListNode start=res;
		ListNode end=res;
		while (end!=null&&end.next!=null){
			end=end.next;
			t++;
			if(t==k){
				//保存下一个节点
				ListNode next=end.next;
				//也是翻转后的最后一个节点，翻转前的第一个节点
				ListNode begin=start.next;
				//反转
				start.next=reverse(begin,next);
				//连接反转后的分组与下一个分组
				begin.next=next;
				t=0;
				//更新新的start和end为下一个分组的前一个节点
				start=begin;
				end=start;
			}
		}
		return res.next;
	}
	//将不包末端点的翻转，最后返回头结点即翻转前的最后一个位置
	private ListNode reverse3(ListNode start,ListNode end){
		ListNode p=start;
		ListNode pre=null;
		while (p!=end&&p!=null){
			ListNode next = p.next;
			p.next=pre;
			pre=p;
			p=next;
		}
		return pre;
	}


	/*链表分区为已翻转部分+待翻转部分+未翻转部分
	每次翻转前，要确定翻转链表的范围，这个必须通过 k 此循环来确定
	需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来
	初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾
	经过k此循环，end 到达末尾，记录待翻转链表的后继 next = end.next
	翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环
	特殊情况，当翻转部分长度不足 k 时，在定位 end 完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可
	时间复杂度为 O(n∗K)最好的情况为 O(n)最差的情况未 O(n2)
	空间复杂度为 O(1) 除了几个必须的节点指针外，我们并没有占用其他空间
。*/
	public ListNode reverseKGroup1(ListNode head, int k) {
		ListNode res = new ListNode(0);
		res.next=head;
		ListNode pre=res;
		ListNode end=res;
		while (end.next!=null){
			for (int i = 0; i < k&&end!=null; i++) {
				end=end.next;
			}
			if(end==null) break;
			ListNode start = pre.next;
			ListNode next = end.next;
			end.next=null;
			pre.next=reverse1(start);
			start.next=next;
			pre=start;
			end=pre;
		}
		return res.next;
	}
	private ListNode reverse1(ListNode head){
		ListNode pre=null;
		ListNode curr=head;
		while (curr!=null){
			ListNode next = head.next;
			curr.next=pre;
			pre=curr;
			curr=next;
		}
		return pre;
	}
	public ListNode reverseKGroup(ListNode head, int k) {
		ListNode res=new ListNode(0,head);
		ListNode pre=res;
		ListNode p=res;
		while (p.next!=null){
			for (int i = 0; i < k&&p!=null; i++) {
				p=p.next;
			}
			if(p==null) break;
			//翻转部分开始
			ListNode start=pre.next;
			ListNode end=p.next;
			//拼接
			pre.next=reverse(start,end);
			start.next=end;
			p=start;
			pre=start;
		}
		return res.next;
	}
	public ListNode reverse(ListNode n1,ListNode n2){
		ListNode node=n1;
		ListNode pre=null;
		while (n1!=n2&&n1!=null){
			ListNode ne=n1.next;
			n1.next=pre;
			pre=n1;
			n1=ne;
		}
		return pre;
	}

}

//leetcode submit region end(Prohibit modification and deletion)

}
